package MapandSetHomeWork;

import java.util.HashMap;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
    }
}
public class CopyRandomList {
    //百度笔试题，LeetCode 138
    public Node copyRandomList(Node head) {
           //首先根据旧结点的位置
           Node cur = head;
           HashMap<Node,Node> hashMap = new HashMap<>();

           while(cur != null) {
               Node newCur = new Node(cur.val);
               hashMap.put(cur,newCur);
               cur = cur.next;
           }

           //让cur再次指回原链表的头部
           cur = head;
           Node newHead = hashMap.get(cur);

           while(cur != null) {
               hashMap.get(cur).next = hashMap.get(cur.next);
               hashMap.get(cur).random = hashMap.get(cur.random);
               cur = cur.next;
           }

           return newHead;
    }
}
